/**
 * 
 */
package leetCode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @author zhong
 *
 */
public class EmployeeFreeTime {
	class Interval {
		int start;
		int end;

		Interval() {
			start = 0;
			end = 0;
		}

		Interval(int s, int e) {
			start = s;
			end = e;
		}

		@Override
		public String toString() {
			return start + "," + end;
		}
	}

	class Node {
		int start, end;
		Node left, right;

		public Node(int a, int b) {
			start = a;
			end = b;
		}

	}

	Node construct(int a, int b) {
		if (a >= b) {
			return null;
		}
		Node node = new Node(a, b);
		int mid = a + (b - a) / 2;
		node.left = construct(a, mid);
		node.right = construct(mid, b);
		return node;
	}

	public List<Interval> employeeFreeTime(List<List<Interval>> avails) {
		// 构建区间树，带Boolean
		List<Interval> intervals = new ArrayList<>();
		int min = Integer.MAX_VALUE;
		int max = -1;
		for (List<Interval> list : avails) {
			for (Interval interval : list) {
				int s = interval.start;
				int e = interval.end;
				min = Math.min(s, min);
				max = Math.max(max, e);
				boolean put = false;
				for (int i = 0; i < intervals.size(); i++) {
					Interval interval2 = intervals.get(i);
					int p = interval2.start;
					int q = interval2.end;
					if (e < p || q < s) {
						continue;
					}
					if (p <= s) {
						if (e > q) {
							// 更新p，e
							interval2.end = e;
							// 删除所有后面被覆盖的

						} // 否则，被覆盖，无需处理
					} else {// 更新为s,Max(e,q)
						interval2.start = s;
						if (q < e)
							interval2.end = e;
					}
					put = true;
					break;
				}
				if (!put) {
					intervals.add(new Interval(s, e));
				}
			}
		}

		List<Interval> res = new ArrayList<>();
		// 对每个区间，找到没有说到过的区间
		int s = -1, e = -1;
		Collections.sort(intervals, (a, b) -> (a.start - b.start));
		for (Interval interval : intervals) {
			e = interval.start;
			int end = interval.end;
			if (e != min) {
				Interval addedIntev = new Interval(s, e);
				res.add(addedIntev);
			}
			s = end;
		}
		return res;
	}

	/**
	 * 使用二分搜索的方法来实现
	 * 
	 * @param avails
	 * @return
	 */
	public List<Interval> employeeFreeTimeBST(List<List<Interval>> avails) {
		Node root = null;
		int start = Integer.MAX_VALUE;
		for (List<Interval> list : avails) {
			for (Interval interval : list) {
				if (root == null) {
					root = new Node(interval.start, interval.end);
				} else {
					// 搜索，插入合适的位置
					insert(root, interval.start, interval.end);
				}
				start = Math.min(start, interval.start);
			}
		}
		// 用先序遍历得到空隙
		List<Interval> res = new ArrayList<>();
		traverse(root, res, start);
		return res;
	}

	private int traverse(Node root, List<Interval> res, int start) {
		if (root == null) {
			return start;
		}
		start = traverse(root.left, res, start);
		if (root.start != start) {
			res.add(new Interval(start, root.start));
		}
		start = root.end;
		start = traverse(root.right, res, start);
		return start;
	}

	private Node insert(Node root, int p, int q) {
		if (p >= q) {
			return root;
		}
		if (root == null) {
			return new Node(p, q);
		}
		int i = root.start, j = root.end;
		if (p > j) {
			root.right = insert(root.right, p, q);
		} else if (q < i) {
			root.left = insert(root.left, p, q);
		} else {
			root.left = insert(root.left, p, i);
			root.right = insert(root.right, j, q);
		}
		return root;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[][][] avail = { { { 1, 3 }, { 6, 7 } }, { { 2, 4 } }, { { 2, 5 }, { 9, 12 } } };
		EmployeeFreeTime employeeFreeTime = new EmployeeFreeTime();
		List<List<Interval>> avails = employeeFreeTime.arr2List(avail);
		System.out.println(employeeFreeTime.employeeFreeTimeBST(avails));
	}

	private List<List<Interval>> arr2List(int[][][] avail) {
		List<List<Interval>> res = new ArrayList<>();
		for (int[][] is : avail) {
			List<Interval> list = new ArrayList<>();
			for (int[] is2 : is) {
				list.add(new Interval(is2[0], is2[1]));
			}
			res.add(list);
		}
		return res;
	}

}
